// xtree internal header -*-c++-*-
// Copyright 2003-2010 IAR Systems AB. 
#ifndef _XTREE_
#define _XTREE_

#ifndef _SYSTEM_BUILD
#pragma system_include
#endif

#include <functional>
#include <memory>
#include <stdexcept>
#define _GENERIC_BASE  _Node

#ifndef _XTREE_BYTE_FIELD
#define _XTREE_BYTE_FIELD(_X) char
#endif

_STD_BEGIN

#pragma language = extended
template <class _Alloc, typename _MemTy>
struct _MkMemAlloc
{				// helper class to make allocator
  typedef typename _TypeUtil::_CopyMemory< _MemTy, void >::_Type _Mem;
  typedef typename _Alloc::template rebind< _Mem >::other _Type;
};

template <class _Alloc, typename _Ty>
struct _MkMemRef
{
  typedef typename _TypeUtil::_CopyMemory<
    typename _Alloc::value_type,
    _Ty
  >::_Type _TyPtrRef;
  typedef _TyPtrRef & _Type;
};


template <class _Alloc, typename _Ty>
struct _MkMemConstRef
{
  typedef typename _TypeUtil::_CopyMemory<
    typename _Alloc::value_type,
    _Ty
  >::_Type _TyPtrRef;
  typedef _TyPtrRef const & _Type;
};

// Class holding all key and value independent code.
template<typename _Alloc>
struct __memory_of(typename _Alloc::value_type) _Tree_algobase
:  _ClassUtil::_AllocHolder<_Alloc, !_ClassUtil::_IsZeroSize<_Alloc>::_Result>
{
protected:
  struct __memory_of(typename _Alloc::value_type) _GenNode;
  friend struct __memory_of(typename _Alloc::value_type) _GenNode;

  typedef typename _Alloc::template rebind< _GenNode >::other _GnalTy;

//  typedef typename _GnalTy::pointer _Genptr;
  typedef _GenNode * _Genptr;
  typedef typename _GnalTy::size_type size_type;

  _GnalTy _Alty () { return _GnalTy(this->_Alval()); }

  typedef typename _MkMemRef<_Alloc, char>::_Type _RawCharref;

  struct __memory_of(typename _Alloc::value_type) _GenNode
  {       // tree node
    _GenNode(_Genptr _Larg, _Genptr _Parg, _Genptr _Rarg, char _Carg)
      : _Left(_Larg), _Parent(_Parg), _Right(_Rarg),
        _Color(_Carg), _Isnil(false)
    {}      // construct a node
    enum _NoInit { kNoInit };
    _GenNode(_NoInit)
    {}      // No initialization

    void swap(_GenNode & _X)
    {
      _STD swap(_Left,   _X._Left);
      _STD swap(_Parent, _X._Parent);
      _STD swap(_Right,  _X._Right);
      _STD swap(_Color,  _X._Color);
      _STD swap(_Isnil,  _X._Isnil);
    }

    _Genptr _Left;  // left subtree, or smallest element if head
    _Genptr _Parent;        // parent, or root of tree if head
    _Genptr _Right; // right subtree, or largest element if head

    typedef typename _MkMemRef<_Alloc, char>::_Type _RawCharref;

    _XTREE_BYTE_FIELD(_RawCharref) _Color;// _Red or _Black, _Black if head
    _XTREE_BYTE_FIELD(_RawCharref) _Isnil;// true only if head (also nil) node
  protected:
    ~_GenNode()       // To protect against dangerous deletion
    {}

    friend struct _Tree_algobase;
  };

  typedef _Alloc allocator_type;
  enum _Redbl
  {       // colors for link to parent
    _Red, _Black};
  //  typedef _REFERENCE_X(_Genptr, allocator_type) _Genpref;
  typedef typename _MkMemRef<allocator_type, _Genptr>::_Type _Genpref;

//  typedef _REFERENCE_X(char, allocator_type) _Charref;
  typedef typename
    _MkMemRef<allocator_type, _XTREE_BYTE_FIELD(_RawCharref)>::_Type _Charref;

  static _Charref _Color(_Genptr _Pnode)
  {       // return reference to color in node
    return ((_Charref)(*_Pnode)._Color);
  }

  static _Charref _Isnil(_Genptr _Pnode)
  {       // return reference to nil flag in node
    return ((_Charref)(*_Pnode)._Isnil);
  }

  static _Genpref _Left(_Genptr _Pnode)
  {       // return reference to left pointer in node
    return ((_Genpref)(*_Pnode)._Left);
  }

  static _Genpref _Parent(_Genptr _Pnode)
  {       // return reference to parent pointer in node
    return ((_Genpref)(*_Pnode)._Parent);
  }

  static _Genpref _Right(_Genptr _Pnode)
  {       // return reference to right pointer in node
    return ((_Genpref)(*_Pnode)._Right);
  }

  static _Genptr _Max(_Genptr _Pnode)
  {       // return rightmost node in subtree at _Pnode
    while (!_Isnil(_Right(_Pnode)))
      _Pnode = _Right(_Pnode);
    return (_Pnode);
  }

  static _Genptr _Min(_Genptr _Pnode)
  {       // return leftmost node in subtree at _Pnode
    while (!_Isnil(_Left(_Pnode)))
      _Pnode = _Left(_Pnode);
    return (_Pnode);
  }

  static _Genptr _DecP(_Genptr _Ptr)
  {
    if (_Isnil(_Ptr))
      return _Right(_Ptr);    // end() ==> rightmost
    else if (!_Isnil(_Left(_Ptr)))
      return _Max(_Left(_Ptr));       // ==> largest of left subtree
    else
    {       // climb looking for left subtree
      _Genptr _Pnode;
      while (!_Isnil(_Pnode = _Parent(_Ptr))
             && _Ptr == _Left(_Pnode))
        _Ptr = _Pnode;  // ==> parent while left subtree
      if (!_Isnil(_Pnode))
        _Ptr = _Pnode;        // ==> parent if not head
    }
    return _Ptr;
  }

  static _Genptr _IncP(_Genptr _Ptr)
  {
    if (_Isnil(_Ptr))
      ;       // end() shouldn't be incremented, don't move
    else if (!_Isnil(_Right(_Ptr)))
      return _Min(_Right(_Ptr));      // ==> smallest of right subtree
    else
    {       // climb looking for right subtree
      _Genptr _Pnode;
      while (!_Isnil(_Pnode = _Parent(_Ptr))
             && _Ptr == _Right(_Pnode))
        _Ptr = _Pnode;  // ==> parent while right subtree
      _Ptr = _Pnode;        // ==> parent (head if end())
    }
    return _Ptr;
  }

  class _GenIter;
  friend class _GenIter;

  class _GenIter
  {       // iterator for generic _Tree
  public:
    _GenIter()
      : _Ptr(0)
    {}      // construct with null node pointer

    _GenIter(_Genptr _Pnode)
      : _Ptr(_Pnode)
    {}      // construct with node pointer _Pnode

    bool operator==(const _GenIter& _Right) const
    {       // test for iterator equality
      return (_Ptr == _Right._Ptr); 
    }

    void _Dec()
    {       // move to node with next smaller value
      _Ptr = _DecP(_Ptr);
    }

    void _Inc()
    {       // move to node with next larger value
      _Ptr = _IncP(_Ptr);
    }

    _Genptr _Mynode() const
    {       // return node pointer
      return (_Ptr); 
    }

  protected:
    _Genptr _Ptr;  // pointer to node
  };

  _Tree_algobase(_Alloc const& _Al)
    : _ClassUtil::_AllocHolder< _Alloc, 
                                !_ClassUtil::_IsZeroSize<_Alloc>::_Result>(_Al),
      _Myhead(_GenNode::kNoInit)
  {
    _Clear();
  }

  void _Clear()
  {
    _Myhead._Parent = &_Myhead;
    _Myhead._Left   = &_Myhead;
    _Myhead._Right  = &_Myhead;
    _Myhead._Isnil  = true;
    _Myhead._Color  = _Black;
    _Mysize = 0;
  }

  _Genpref _Root()
  {       // return root of mutable tree
    return (_Parent(&_Myhead)); 
  }

  _Genpref _Lmost()
  {       // return leftmost node in mutable tree
    return (_Left(&_Myhead)); 
  }

  _Genpref _Rmost()
  {       // return leftmost node in mutable tree
    return (_Right(&_Myhead)); 
  }

  void _Rrotate(_Genptr _Wherenode)
  {       // promote left node to root of subtree
    _Genptr _Pnode = _Left(_Wherenode);
    _Left(_Wherenode) = _Right(_Pnode);

    if (!_Isnil(_Right(_Pnode)))
      _Parent(_Right(_Pnode)) = _Wherenode;
    _Parent(_Pnode) = _Parent(_Wherenode);

    if (_Wherenode == _Root())
      _Root() = _Pnode;
    else if (_Wherenode == _Right(_Parent(_Wherenode)))
      _Right(_Parent(_Wherenode)) = _Pnode;
    else
      _Left(_Parent(_Wherenode)) = _Pnode;

    _Right(_Pnode) = _Wherenode;
    _Parent(_Wherenode) = _Pnode; 
  }

  void _Lrotate(_Genptr _Wherenode)
  {       // promote right node to root of subtree
    _Genptr _Pnode = _Right(_Wherenode);
    _Right(_Wherenode) = _Left(_Pnode);

    if (!_Isnil(_Left(_Pnode)))
      _Parent(_Left(_Pnode)) = _Wherenode;
    _Parent(_Pnode) = _Parent(_Wherenode);

    if (_Wherenode == _Root())
      _Root() = _Pnode;
    else if (_Wherenode == _Left(_Parent(_Wherenode)))
      _Left(_Parent(_Wherenode)) = _Pnode;
    else
      _Right(_Parent(_Wherenode)) = _Pnode;

    _Left(_Pnode) = _Wherenode;
    _Parent(_Wherenode) = _Pnode; 
  }

  _Genptr _Erase(_Genptr _Where)
  {       // erase element at _Where
    if (_Isnil(_Where))
      _THROW(out_of_range, "invalid map/set<T> iterator");
    _Genptr _Fixnode;              // the node to recolor as needed
    _Genptr _Fixnodeparent;        // parent of _Fixnode (which may be nil)
    _Genptr _Erasednode = _Where;  // node to erase
    _Genptr _Pnode = _Erasednode;
    _Where = _IncP(_Where);       // save successor iterator for return

    if (_Isnil(_Left(_Pnode)))
      _Fixnode = _Right(_Pnode);      // must stitch up right subtree
    else if (_Isnil(_Right(_Pnode)))
      _Fixnode = _Left(_Pnode);       // must stitch up left subtree
    else
    {       // two subtrees, must lift successor node to replace erased
      _Pnode = _Where;               // _Pnode is successor node
      _Fixnode = _Right(_Pnode);     // _Fixnode is its only subtree
    }

    if (_Pnode == _Erasednode)
    {       // at most one subtree, relink it
      _Fixnodeparent = _Parent(_Erasednode);
      if (!_Isnil(_Fixnode))
        _Parent(_Fixnode) = _Fixnodeparent;     // link up

      if (_Root() == _Erasednode)
        _Root() = _Fixnode;     // link down from root
      else if (_Left(_Fixnodeparent) == _Erasednode)
        _Left(_Fixnodeparent) = _Fixnode;       // link down to left
      else
        _Right(_Fixnodeparent) = _Fixnode;      // link down to right

      if (_Lmost() == _Erasednode)
        _Lmost() = _Isnil(_Fixnode)
          ? _Fixnodeparent        // smallest is parent of erased node
          : _Min(_Fixnode);       // smallest in relinked subtree

      if (_Rmost() == _Erasednode)
        _Rmost() = _Isnil(_Fixnode)
          ? _Fixnodeparent        // largest is parent of erased node
          : _Max(_Fixnode);      // largest in relinked subtree
    }
    else
    {       // erased has two subtrees, _Pnode is successor to erased
      _Parent(_Left(_Erasednode)) = _Pnode;   // link left up
      _Left(_Pnode) = _Left(_Erasednode);     // link successor down

      if (_Pnode == _Right(_Erasednode))
        _Fixnodeparent = _Pnode;        // successor is next to erased
      else
      {       // successor further down, link in place of erased
        _Fixnodeparent = _Parent(_Pnode);       // parent is successor's
        if (!_Isnil(_Fixnode))
          _Parent(_Fixnode) = _Fixnodeparent;     // link fix up
        _Left(_Fixnodeparent) = _Fixnode;       // link fix down
        _Right(_Pnode) = _Right(_Erasednode);   // link successor down
        _Parent(_Right(_Erasednode)) = _Pnode;         // link right up
      }

      if (_Root() == _Erasednode)
        _Root() = _Pnode;       // link down from root
      else if (_Left(_Parent(_Erasednode)) == _Erasednode)
        _Left(_Parent(_Erasednode)) = _Pnode;   // link down to left
      else
        _Right(_Parent(_Erasednode)) = _Pnode;  // link down to right

      _Parent(_Pnode) = _Parent(_Erasednode); // link successor up
      _STD swap(_Color(_Pnode), _Color(_Erasednode));        // recolor it
    }

    if (_Color(_Erasednode) == _Black)
    {       // erasing black link, must recolor/rebalance tree
      for (; _Fixnode != _Root() && _Color(_Fixnode) == _Black;
           _Fixnodeparent = _Parent(_Fixnode))
        if (_Fixnode == _Left(_Fixnodeparent))
        {       // fixup left subtree
          _Pnode = _Right(_Fixnodeparent);
          if (_Color(_Pnode) == _Red)
          {       // rotate red up from right subtree
            _Color(_Pnode) = _Black;
            _Color(_Fixnodeparent) = _Red;
            _Lrotate(_Fixnodeparent);
            _Pnode = _Right(_Fixnodeparent); 
          }

          if (_Isnil(_Pnode))
            _Fixnode = _Fixnodeparent;      // shouldn't happen
          else if (_Color(_Left(_Pnode)) == _Black
                   && _Color(_Right(_Pnode)) == _Black)
          {       // redden right subtree with black children
            _Color(_Pnode) = _Red;
            _Fixnode = _Fixnodeparent; 
          }
          else
          {       // must rearrange right subtree
            if (_Color(_Right(_Pnode)) == _Black)
            {       // rotate red up from left sub-subtree
              _Color(_Left(_Pnode)) = _Black;
              _Color(_Pnode) = _Red;
              _Rrotate(_Pnode);
              _Pnode = _Right(_Fixnodeparent); 
            }

            _Color(_Pnode) = _Color(_Fixnodeparent);
            _Color(_Fixnodeparent) = _Black;
            _Color(_Right(_Pnode)) = _Black;
            _Lrotate(_Fixnodeparent);
            break;        // tree now recolored/rebalanced
          }
        }
        else
        {       // fixup right subtree
          _Pnode = _Left(_Fixnodeparent);
          if (_Color(_Pnode) == _Red)
          {       // rotate red up from left subtree
            _Color(_Pnode) = _Black;
            _Color(_Fixnodeparent) = _Red;
            _Rrotate(_Fixnodeparent);
            _Pnode = _Left(_Fixnodeparent); 
          }
          if (_Isnil(_Pnode))
            _Fixnode = _Fixnodeparent;      // shouldn't happen
          else if (_Color(_Right(_Pnode)) == _Black
                   && _Color(_Left(_Pnode)) == _Black)
          {       // redden left subtree with black children
            _Color(_Pnode) = _Red;
            _Fixnode = _Fixnodeparent; 
          }
          else
          {       // must rearrange left subtree
            if (_Color(_Left(_Pnode)) == _Black)
            {       // rotate red up from right sub-subtree
              _Color(_Right(_Pnode)) = _Black;
              _Color(_Pnode) = _Red;
              _Lrotate(_Pnode);
              _Pnode = _Left(_Fixnodeparent); 
            }

            _Color(_Pnode) = _Color(_Fixnodeparent);
            _Color(_Fixnodeparent) = _Black;
            _Color(_Left(_Pnode)) = _Black;
            _Rrotate(_Fixnodeparent);
            break;        // tree now recolored/rebalanced
          }
        }

      _Color(_Fixnode) = _Black;     // ensure stopping node is black
    }

    if (0 < this->_Mysize)
      --this->_Mysize;
    return _Erasednode;            // Return ptr to node to destroy
  }

  void _Insert(bool _Addleft, _Genptr _Wherenode, _Genptr _Newnode)
  {       // add node _Newnode next to _Wherenode, to left if _Addnode
    ++this->_Mysize;
    if (_Wherenode == &this->_Myhead)
    {       // first node in tree, just set head values
      _Root() = _Newnode;
      _Lmost() = _Newnode, _Rmost() = _Newnode; 
    }
    else if (_Addleft)
    {       // add to left of _Wherenode
      _Left(_Wherenode) = _Newnode;
      if (_Wherenode == _Lmost())
        _Lmost() = _Newnode;
    }
    else
    {       // add to right of _Wherenode
      _Right(_Wherenode) = _Newnode;
      if (_Wherenode == _Rmost())
        _Rmost() = _Newnode; 
    }

    for (_Genptr _Pnode = _Newnode; _Color(_Parent(_Pnode)) == _Red; )
      if (_Parent(_Pnode) == _Left(_Parent(_Parent(_Pnode))))
      {       // fixup red-red in left subtree
        _Wherenode = _Right(_Parent(_Parent(_Pnode)));
        if (_Color(_Wherenode) == _Red)
        {       // parent has two red children, blacken both
          _Color(_Parent(_Pnode)) = _Black;
          _Color(_Wherenode) = _Black;
          _Color(_Parent(_Parent(_Pnode))) = _Red;
          _Pnode = _Parent(_Parent(_Pnode)); 
        }
        else
        {       // parent has red and black children
          if (_Pnode == _Right(_Parent(_Pnode)))
          {       // rotate right child to left
            _Pnode = _Parent(_Pnode);
            _Lrotate(_Pnode); }
          _Color(_Parent(_Pnode)) = _Black;       // propagate red up
          _Color(_Parent(_Parent(_Pnode))) = _Red;
          _Rrotate(_Parent(_Parent(_Pnode))); 
        }
      }
      else
      {       // fixup red-red in right subtree
        _Wherenode = _Left(_Parent(_Parent(_Pnode)));
        if (_Color(_Wherenode) == _Red)
        {       // parent has two red children, blacken both
          _Color(_Parent(_Pnode)) = _Black;
          _Color(_Wherenode) = _Black;
          _Color(_Parent(_Parent(_Pnode))) = _Red;
          _Pnode = _Parent(_Parent(_Pnode)); 
        }
        else
        {       // parent has red and black children
          if (_Pnode == _Left(_Parent(_Pnode)))
          {       // rotate left child to right
            _Pnode = _Parent(_Pnode);
            _Rrotate(_Pnode); }
          _Color(_Parent(_Pnode)) = _Black;       // propagate red up
          _Color(_Parent(_Parent(_Pnode))) = _Red;
          _Lrotate(_Parent(_Parent(_Pnode))); 
        }
      }

    _Color(_Root()) = _Black;       // root is always black
  }

  _GenNode _Myhead;
  size_type _Mysize;
}; // END TEMPLATE CLASS _Tree_algobase

// TEMPLATE CLASS _Tree_nod
template<class _Traits>
class __memory_of(typename _Traits::value_type) _Tree_nod
: public _Tree_algobase<
  typename _MkMemAlloc< typename _Traits::allocator_type, 
			typename _Traits::value_type >::_Type 
>
{       // class to hold node dependent types and members
protected:
  struct __memory_of(typename _Traits::value_type) _Node;
  friend struct __memory_of(typename _Traits::value_type) _Node;

  typedef typename _Traits::allocator_type _Alloc;
  typedef typename _Alloc::template rebind<_Node>::other _AlnodTy;
  _AlnodTy _Alnod() const { return _AlnodTy(this->_Alval()); }

  typedef _Tree_algobase<
    typename _MkMemAlloc<typename _Traits::allocator_type, 
			 typename _Traits::value_type>::_Type
  > _Mybase;

  typedef _Alloc allocator_type;

  typedef typename _Traits::key_compare key_compare;
  typedef typename _Traits::value_type value_type;

  typedef typename _Traits::_KeyParamTy _KeyParamTy;
  typedef typename _Traits::_ValParamTy _ValParamTy;

  typedef typename _Alloc::template rebind< _Node >::other
  _MyGenal;			// node allocator type

//  typedef typename _MyGenal::pointer _MyGenptr;
  typedef typename _TypeUtil::_CopyMemory<
    typename _Traits::value_type, 
    _Node
  >::_Type * _MyGenptr;

  key_compare   comp() const { return _Kcmp; }
  key_compare & comp()       { return _Kcmp; }

  typedef typename _Traits::key_type key_type;

  enum
  {
    _Multi = _Traits::_Multi
  };

  struct __memory_of(typename _Traits::value_type) _Node
    : _Mybase::_GenNode
  {       // tree node
    _Node(_MyGenptr _Larg, _MyGenptr _Parg, _MyGenptr _Rarg,
          _ValParamTy _Val, char _Carg)
      : _Mybase::_GenNode(_Larg, _Parg, _Rarg, _Carg),
        _Myval(_Val)
    {}      // construct a node with value

    typename _TypeUtil::_StripMemory<typename _Traits::value_type>::_Type
      _Myval;      // the stored value, unused if head
  };

  _Tree_nod(const key_compare& _Parg,
            _Alloc _Al)
    : _Mybase(_Al), _Kcmp(_Parg)
  {}      // pass _Al to _Tree_algobase and initialize _Kcmp from _Parg

  _ClassUtil::_MemHolder<typename _Traits::value_type ,key_compare> _Kcmp;
};

// TEMPLATE CLASS _Tree_val
template<class _Traits>
class _Tree_val
  : public _Tree_nod< _Traits >
{       // base class for _Tree contain value_type specific support
protected:
  typedef _Tree_nod< _Traits > _Mybase;

  typedef typename _Mybase::allocator_type allocator_type;
  typedef typename _Mybase::key_compare key_compare;
  typedef typename _Mybase::key_type key_type;

  typedef typename _Traits::value_type value_type;

  typedef typename _Mybase::_KeyParamTy _KeyParamTy;
  typedef typename _Mybase::_ValParamTy _ValParamTy;

  _Tree_val(const key_compare& _Parg,
            allocator_type _Al)
    : _Tree_nod<_Traits>(_Parg, _Al)
  {}      // construct base, and allocator from _Al


  static _KeyParamTy _Kfn(_ValParamTy _Val)
  {
    return _Traits::_Kfn(_Val);
  }

#if 0
  allocator_type _Alval() const
  { // allocator object for values stored in nodes
    return allocator_type(this->_Myhead);
  }
#endif
};

// TEMPLATE CLASS _Tree
template<class _Traits>
class _Tree
  : public _Tree_val<_Traits>
{       // ordered red-black tree for [multi_]{map set}
public:
  typedef _Tree<_Traits> _Myt;
  typedef _Tree_val<_Traits> _Mybase;

  typedef typename _Mybase::key_compare key_compare;
  typedef typename _Mybase::value_type value_type;
  typedef typename _Mybase::allocator_type allocator_type;

  typedef typename _Traits::key_type key_type;
  typedef typename _Traits::value_compare value_compare;
  typedef typename _Traits::_ITptr _ITptr;
  typedef typename _Traits::_IReft _IReft;

protected:
  typedef typename _Mybase::_Genptr _Genptr;
  typedef typename _Tree_nod<_Traits>::_Node _Node;

  typedef typename _Mybase::_KeyParamTy _KeyParamTy;
  typedef typename _Mybase::_ValParamTy _ValParamTy;

  typedef typename _Traits::allocator_type _Alloc;

  typedef typename _Alloc::template rebind<_Node>::other _AlNodTy;
  _AlNodTy _Alnod() const { return _AlNodTy(this->_Alval()); }

  enum _Redbl
  {       // colors for link to parent
    _Red, _Black};
//  typedef _POINTER_X(_Node, allocator_type) _Nodeptr;
#pragma important_typedef
  typedef _Node * _Nodeptr;

//  typedef _REFERENCE_X(_Nodeptr, allocator_type) _Nodepref;
  typedef typename _MkMemRef<allocator_type, _Nodeptr>::_Type _Nodepref;

  typedef typename _MkMemRef<allocator_type, char>::_Type _RawCharref;

//  typedef _REFERENCE_X(char, allocator_type) _Charref;
  typedef typename
  _MkMemRef<allocator_type, _XTREE_BYTE_FIELD(_RawCharref)>::_Type _Charref;

//  typedef _REFERENCE_X(value_type, allocator_type) _Valref;
  typedef typename _MkMemRef<allocator_type, value_type>::_Type _Valref;

  static _Charref _Color(_Genptr _Pnode)
  {       // return reference to color in node
    return _Mybase::_Color(_Pnode);
  }

  static _Charref _Isnil(_Genptr _Pnode)
  {       // return reference to nil flag in node
    return _Mybase::_Isnil(_Pnode);
  }

  static _KeyParamTy _Key(_Genptr _Pnode)
  {       // return reference to key in node
    return (_Mybase::_Kfn(_Myval(_Pnode))); 
  }

  static _Nodepref _Left(_Genptr _Pnode)
  {       // return reference to left pointer in node
    return ((_Nodepref)(*_Pnode)._Left); 
  }

  static _Nodepref _Parent(_Genptr _Pnode)
  {       // return reference to parent pointer in node
    return ((_Nodepref)(*_Pnode)._Parent); 
  }

  static _Nodepref _Right(_Genptr _Pnode)
  {       // return reference to right pointer in node
    return ((_Nodepref)(*_Pnode)._Right); 
  }

  static _Valref _Myval(_Genptr _Pnode)
  {       // return reference to value in node
    return ((_Valref)(*static_cast<_Nodeptr>(_Pnode))._Myval); 
  }

public:
  typedef typename allocator_type::size_type size_type;
  typedef typename allocator_type::difference_type _Dift;
  typedef _Dift difference_type;
  typedef _POINTER_X(value_type, allocator_type) _Tptr;
  typedef _CPOINTER_X(value_type, allocator_type) _Ctptr;
  typedef _REFERENCE_X(value_type, allocator_type) _Reft;
  typedef _Tptr pointer;
  typedef _Ctptr const_pointer;
  typedef _Reft reference;
  typedef _CREFERENCE_X(value_type, allocator_type) const_reference;

  // CLASS const_iterator
  class const_iterator;
  friend class const_iterator;

  class const_iterator
    : public _Bidit<value_type, _Dift, _Ctptr, const_reference>
  {       // iterator for nonmutable _Tree
  public:
    typedef bidirectional_iterator_tag iterator_category;
    typedef _Dift difference_type;
    typedef _Ctptr pointer;
    typedef const_reference reference;
#pragma important_typedef
    typedef _Nodeptr _Nodeptr;

    const_iterator()
      : _GIter()
    {}      // construct with null node pointer

    const_iterator(_Genptr _Pnode)
      : _GIter(_Pnode)
    {}      // construct with node pointer _Pnode

    const_reference operator*() const
    {       // return designated value
      return (_Myval(_GIter._Mynode()));
    }

    _Ctptr operator->() const
    {       // return pointer to class object
      return (&**this); 
    }

    const_iterator& operator++()
    {       // preincrement
      _GIter._Inc();
      return (*this); 
    }

    const_iterator operator++(int)
    {       // postincrement
      const_iterator _Tmp = *this;
      ++*this;
      return (_Tmp); 
    }

    const_iterator& operator--()
    {       // predecrement
      _GIter._Dec();
      return (*this); 
    }

    const_iterator operator--(int)
    {       // postdecrement
      const_iterator _Tmp = *this;
      --*this;
      return (_Tmp); 
    }

    bool operator==(const const_iterator& _Right) const
    {       // test for iterator equality
      return (_GIter == _Right._GIter); 
    }

    bool operator!=(const const_iterator& _Right) const
    {       // test for iterator inequality
      return (!(*this == _Right)); 
    }

    _Nodeptr _Mynode() const
    {       // return node pointer
      return static_cast<_Nodeptr>(_GIter._Mynode());
    }

  protected:
    typename _Mybase::_GenIter _GIter;
  };

  // CLASS iterator
  class iterator;
  friend class iterator;

  class iterator
    : public const_iterator
  {       // iterator for mutable _Tree
  public:
    typedef bidirectional_iterator_tag iterator_category;
    typedef _Dift difference_type;
    typedef _ITptr pointer;
    typedef _IReft reference;
#pragma important_typedef
    typedef _Nodeptr _Nodeptr;

    iterator()
      : const_iterator(0)
    {}      // construct with null node pointer

    iterator(_Genptr _Pnode)
      : const_iterator(_Pnode)
    {}      // construct with node pointer _Pnode

    reference operator*() const
    {       // return designated value
      return (_Myval(this->_GIter._Mynode()));
    }

    pointer operator->() const
    {       // return pointer to class object
      return (&**this); 
    }

    iterator& operator++()
    {       // preincrement
      this->_GIter._Inc();
      return (*this);
    }

    iterator operator++(int)
    {       // postincrement
      iterator _Tmp = *this;
      ++*this;
      return (_Tmp); 
    }

    iterator& operator--()
    {       // predecrement
      this->_GIter._Dec();
      return (*this);
    }

    iterator operator--(int)
    {       // postdecrement
      iterator _Tmp = *this;
      --*this;
      return (_Tmp); 
    }
  };

  typedef _STD reverse_iterator<iterator> reverse_iterator;
  typedef _STD reverse_iterator<const_iterator> const_reverse_iterator;
  typedef pair<iterator, bool> _Pairib;
  typedef pair<iterator, iterator> _Pairii;
  typedef pair<const_iterator, const_iterator> _Paircc;

  explicit _Tree(const key_compare& _Parg,
                 const allocator_type& _Al)
    : _Mybase(_Parg, _Al)
  {       // construct empty tree
  }

  _Tree(const value_type *_First, const value_type *_Last,
        const key_compare& _Parg, const allocator_type& _Al)
    : _Mybase(_Parg, _Al)
  {       // construct tree from [_First, _Last) array
    _TRY_BEGIN
      insert(_First, _Last);
    _CATCH_ALL
      clear();
    _RERAISE;
    _CATCH_END 
  }

  _Tree(const _Myt& _Right)
    : _Mybase(_Right.key_comp(), _Right.get_allocator())
  {       // construct tree by copying _Right
    _TRY_BEGIN
      _Copy(_Right);
    _CATCH_ALL
      clear();
    _RERAISE;
    _CATCH_END 
  }

  ~_Tree()
  {       // destroy tree
    clear(); 
  }

  _Myt& operator=(const _Myt& _Right)
  {       // replace contents from _Right
    if (this != &_Right)
    {       // worth doing
      erase(begin(), end());
      this->comp() = _Right.comp();
      _Copy(_Right); }
    return (*this); 
  }

  iterator begin()
  {       // return iterator for beginning of mutable sequence
    return (iterator(_Lmost())); 
  }

  const_iterator begin() const
  {       // return iterator for beginning of nonmutable sequence
    return (const_iterator(_Lmost())); 
  }

  iterator end()
  {       // return iterator for end of mutable sequence
    return (iterator(&this->_Myhead)); 
  }

  const_iterator end() const
  {       // return iterator for end of nonmutable sequence
    return (const_iterator(const_cast<typename _Mybase::_Genptr>(
                                                        &this->_Myhead)));
  }

  reverse_iterator rbegin()
  {       // return iterator for beginning of reversed mutable sequence
    return (reverse_iterator(end())); 
  }

  const_reverse_iterator rbegin() const
  {       // return iterator for beginning of reversed nonmutable sequence
    return (const_reverse_iterator(end())); 
  }

  reverse_iterator rend()
  {       // return iterator for end of reversed mutable sequence
    return (reverse_iterator(begin())); 
  }

  const_reverse_iterator rend() const
  {       // return iterator for end of reversed nonmutable sequence
    return (const_reverse_iterator(begin())); 
  }

  size_type size() const
  {       // return length of sequence
    return (this->_Mysize); 
  }

  size_type max_size() const
  {       // return maximum possible length of sequence
    return (this->_Alnod().max_size()); 
  }

  bool empty() const
  {       // return true only if sequence is empty
    return (size() == 0); 
  }

  allocator_type get_allocator() const
  {       // return allocator object for values
    return (this->_Alval()); 
  }

  key_compare key_comp() const
  {       // return object for comparing keys
    return (this->comp()); 
  }

  value_compare value_comp() const
  {       // return object for comparing values
    return (value_compare(key_comp())); 
  }

  _Pairib insert(_ValParamTy _Val)
  {       // try to insert node with value _Val
    _Nodeptr _Trynode = _Root();
    _Nodeptr _Wherenode = _Head();
    bool _Addleft = true;   // add to left of head if tree empty
    while (!_Isnil(_Trynode))
    {       // look for leaf to insert before (_Addleft) or after
      _Wherenode = _Trynode;
      _Addleft = this->comp()(this->_Kfn(_Val), _Key(_Trynode));
      _Trynode = _Addleft ? _Left(_Trynode) : _Right(_Trynode); 
    }

    if (this->_Multi)
      return (_Pairib(_Insert(_Addleft, _Wherenode, _Val), true));
    else
    {       // insert only if unique
      iterator _Where = iterator(_Wherenode);
      if (!_Addleft)
        ;       // need to test if insert after is okay
      else if (_Where == begin())
        return (_Pairib(_Insert(true, _Wherenode, _Val), true));
      else
        --_Where;       // need to test if insert before is okay

      if (this->comp()(_Key(_Where._Mynode()), this->_Kfn(_Val)))
        return (_Pairib(_Insert(_Addleft, _Wherenode, _Val), true));
      else
        return (_Pairib(_Where, false)); 
    }
  }

  iterator insert(iterator _Where, _ValParamTy _Val)
  {       // try to insert node with value _Val using _Where as a hint
    iterator _Next;

    if (size() == 0)
      return (_Insert(true, _Head(), _Val));  // insert into empty tree
    else if (this->_Multi)
    {       // insert even if duplicate
      if (_Where == begin())
      {       // insert at beginning if before first element
        if (!this->comp()(_Key(_Where._Mynode()), this->_Kfn(_Val)))
          return (_Insert(true, _Where._Mynode(), _Val)); 
      }
      else if (_Where == end())
      {       // insert at end if after last element
        if (!this->comp()(this->_Kfn(_Val), _Key(_Rmost())))
          return (_Insert(false, _Rmost(), _Val)); 
      }
      else if (!this->comp()(_Key(_Where._Mynode()), this->_Kfn(_Val))
               && !this->comp()(this->_Kfn(_Val),
                              _Key((--(_Next = _Where))._Mynode())))
      {       // insert before _Where
        if (_Isnil(_Right(_Next._Mynode())))
          return (_Insert(false, _Next._Mynode(), _Val));
        else
          return (_Insert(true, _Where._Mynode(), _Val)); 
      }
      else if (!this->comp()(this->_Kfn(_Val), _Key(_Where._Mynode()))
               && (++(_Next = _Where) == end()
                   || !this->comp()(_Key(_Next._Mynode()),
                                  this->_Kfn(_Val))))
      {       // insert after _Where
        if (_Isnil(_Right(_Where._Mynode())))
          return (_Insert(false, _Where._Mynode(), _Val));
        else
          return (_Insert(true, _Next._Mynode(), _Val)); 
      }
    }
    else
    {       // insert only if unique
      if (_Where == begin())
      {       // insert at beginning if before first element
        if (this->comp()(this->_Kfn(_Val), _Key(_Where._Mynode())))
          return (_Insert(true, _Where._Mynode(), _Val));
      }
      else if (_Where == end())
      {       // insert at end if after last element
        if (this->comp()(_Key(_Rmost()), this->_Kfn(_Val)))
          return (_Insert(false, _Rmost(), _Val)); 
      }
      else if (this->comp()(this->_Kfn(_Val), _Key(_Where._Mynode()))
               && this->comp()(_Key((--(_Next = _Where))._Mynode()),
                             this->_Kfn(_Val)))
      {       // insert before _Where
        if (_Isnil(_Right(_Next._Mynode())))
          return (_Insert(false, _Next._Mynode(), _Val));
        else
          return (_Insert(true, _Where._Mynode(), _Val)); 
      }
      else if (this->comp()(_Key(_Where._Mynode()), this->_Kfn(_Val))
               && (++(_Next = _Where) == end()
                   || this->comp()(this->_Kfn(_Val),
                                 _Key(_Next._Mynode()))))
      {       // insert after _Where
        if (_Isnil(_Right(_Where._Mynode())))
          return (_Insert(false, _Where._Mynode(), _Val));
        else
          return (_Insert(true, _Next._Mynode(), _Val)); 
      }
    }

    return (insert(_Val).first);   // try usual insert if all else fails
  }

  template<class _Iter>
  _ALLOW_ONLY_ITERATORS(_Iter, void)
  insert(_Iter _First, _Iter _Last)
  {
    // insert [_First, _Last) one at a time
    typedef _ClassUtil::_TmpHolder<value_type> _TmpH;
    typedef typename _TmpH::_Type _Holder;
    if (_TmpH::_OnHeap) {
      _Holder _Val(*_First);
      for (; _First != _Last; ++_First) {
        // This is just to make things compile in some cases where this
        // branch is not taken.
        typename _TypeUtil::_Select<_TmpH::_OnHeap, _ValParamTy,
                                                    _Holder &>::_Type _P = _Val;
        _ReAssign(&_P, *_First);
        insert(_Val); 
      }
    } else {
      for (; _First != _Last; ++_First) {
        insert(_Holder(*_First));
      }
    }
  }

  iterator erase(iterator _Where)
  {       // erase element at _Where
    iterator _Result = _Where;
    ++_Result;       // save successor iterator for return
    _Nodeptr _Erasednode =
                    static_cast<_Nodeptr>(_Mybase::_Erase(_Where._Mynode()));

    this->_Alnod().destroy(_Erasednode);      // destroy, free erased node
    this->_Alnod().deallocate(_Erasednode, 1);

    return (_Result);       // return successor iterator
  }

  iterator erase(iterator _First, iterator _Last)
  {       // erase [_First, _Last)
    if (_First == begin() && _Last == end())
    {       // erase all
      clear();
      return (begin()); 
    }
    else
    {       // partial erase, one at a time
      while (_First != _Last)
        erase(_First++);
      return (_First); 
    }
  }

  size_type erase(_KeyParamTy _Keyval)
  {       // erase and count all that match _Keyval
    _Pairii _Where = equal_range(_Keyval);
    size_type _Num = distance(_Where.first, _Where.second);
    erase(_Where.first, _Where.second);
    return (_Num); 
  }

  void erase(const key_type *_First, const key_type *_Last)
  {       // erase all that match array of keys [_First, _Last)
    while (_First != _Last)
      erase(*_First++); 
  }

  void clear()
  {       // erase all
    _Erase(_Root());
    _Mybase::_Clear();
  }

  iterator find(_KeyParamTy _Keyval)
  {       // find an element in mutable sequence that matches _Keyval
    iterator _Where = lower_bound(_Keyval);
    return (_Where == end() || this->comp()(_Keyval, _Key(_Where._Mynode()))
            ? end() : _Where); 
  }

  const_iterator find(_KeyParamTy _Keyval) const
  {       // find an element in nonmutable sequence that matches _Keyval
    const_iterator _Where = lower_bound(_Keyval);
    return (_Where == end() || this->comp()(_Keyval, _Key(_Where._Mynode()))
            ? end() : _Where); 
  }

  size_type count(_KeyParamTy _Keyval) const
  {       // count all elements that match _Keyval
    _Paircc _Ans = equal_range(_Keyval);
    size_type _Num = distance(_Ans.first, _Ans.second);
    return (_Num); 
  }

  iterator lower_bound(_KeyParamTy _Keyval)
  {       // find leftmost node not less than _Keyval in mutable tree
    return (iterator(_Lbound(_Keyval))); 
  }

  const_iterator lower_bound(_KeyParamTy _Keyval) const
  {       // find leftmost node not less than _Keyval in nonmutable tree
    return (const_iterator(_Lbound(_Keyval))); 
  }

  iterator upper_bound(_KeyParamTy _Keyval)
  {       // find leftmost node greater than _Keyval in mutable tree
    return (iterator(_Ubound(_Keyval))); 
  }

  const_iterator upper_bound(_KeyParamTy _Keyval) const
  {       // find leftmost node greater than _Keyval in nonmutable tree
    return (const_iterator(_Ubound(_Keyval))); 
  }

  _Pairii equal_range(_KeyParamTy _Keyval)
  {       // find range equivalent to _Keyval in mutable tree
    return (_Pairii(lower_bound(_Keyval), upper_bound(_Keyval))); 
  }

  _Paircc equal_range(_KeyParamTy _Keyval) const
  {       // find range equivalent to _Keyval in nonmutable tree
    return (_Paircc(lower_bound(_Keyval), upper_bound(_Keyval))); 
  }

  void swap(_Myt& _Right)
  {       // exchange contents with _Right
    if (get_allocator() == _Right.get_allocator())
    {       // same allocator, swap control information
      _STD swap(this->comp(), _Right.comp());
      this->_Myhead.swap(_Right._Myhead);
      _STD swap(this->_Mysize, _Right._Mysize); 
    }
    else
    {       // different allocator, do multiple assigns
      _Myt _Tmp = *this; *this = _Right, _Right = _Tmp; 
    }
  }

protected:
  void _Copy(const _Myt& _Right)
  {       // copy entire tree from _Right
    _Root() = _Copy(_Right._Root(), _Head());
    this->_Mysize = _Right.size();
    if (!_Isnil(_Root()))
    {       // nonempty tree, look for new smallest and largest
      _Lmost() = _Min(_Root());
      _Rmost() = _Max(_Root()); 
    }
    else
      _Lmost() = _Head(), _Rmost() = _Head();        // empty tree
  }

  _Nodeptr _Copy(_Nodeptr _Rootnode, _Nodeptr _Wherenode)
  {       // copy entire subtree, recursively
    _Nodeptr _Newroot = _Head();    // point at nil node

    if (!_Isnil(_Rootnode))
    {       // copy a node, then any subtrees
      _Nodeptr _Pnode = _Buynode(_Head(), _Wherenode, _Head(),
                                 _Myval(_Rootnode), _Color(_Rootnode));
      if (_Isnil(_Newroot))
        _Newroot = _Pnode;      // memorize new root

      _TRY_BEGIN
        _Left(_Pnode) = _Copy(_Left(_Rootnode), _Pnode);
      _Right(_Pnode) = _Copy(_Right(_Rootnode), _Pnode);
      _CATCH_ALL
        _Erase(_Newroot);       // subtree copy failed, bail out
      _RERAISE;
      _CATCH_END 
    }

    return (_Newroot);     // return newly constructed tree
  }

  void _Erase(_Nodeptr _Rootnode)
  {       // free entire subtree, recursively
    for (_Nodeptr _Pnode = _Rootnode; !_Isnil(_Pnode); _Rootnode = _Pnode)
    {       // free subtrees, then node
      _Erase(_Right(_Pnode));
      _Pnode = _Left(_Pnode);
#if 1
      this->_Alnod().destroy(_Rootnode);        // destroy, free erased node
      this->_Alnod().deallocate(_Rootnode, 1); 
#else
      _Mybase::_MyGenal(this->_Myhead).destroy(_Rootnode);	// destroy, free erased node
      _Mybase::_MyGenal(this->_Myhead).deallocate(_Rootnode, 1); 
#endif
    }
  }

  iterator _Insert(bool _Addleft, _Nodeptr _Wherenode, _ValParamTy _Val)
  {       // add node with value next to _Wherenode, to left if _Addnode
    if (max_size() - 1 <= this->_Mysize)
      _THROW(length_error, "map/set<T> too long");
    _Nodeptr _Newnode = _Buynode(_Head(), _Wherenode, _Head(),
                                 _Val, _Red);

    _Mybase::_Insert(_Addleft, _Wherenode, _Newnode);
    return (iterator(_Newnode)); 
  }

  _Nodeptr _Lbound(_KeyParamTy _Keyval) const
  {       // find leftmost node not less than _Keyval
    _Nodeptr _Pnode = _Root();
    _Nodeptr _Wherenode = _Head();  // end() if search fails

    while (!_Isnil(_Pnode))
      if (this->comp()(_Key(_Pnode), _Keyval))
        _Pnode = _Right(_Pnode);        // descend right subtree
      else
      {       // _Pnode not less than _Keyval, remember it
        _Wherenode = _Pnode;
        _Pnode = _Left(_Pnode);        // descend left subtree
      }

    return (_Wherenode);   // return best remembered candidate
  }

  _Nodepref _Lmost()
  {       // return leftmost node in mutable tree
    return (_Left(_Head())); 
  }

  _Nodepref _Lmost() const
  {       // return leftmost node in nonmutable tree
    return (_Left(_Head())); 
  }

  void _Lrotate(_Nodeptr _Wherenode)
  {       // promote right node to root of subtree
    _Mybase::_Lrotate(_Wherenode);
  }

  static _Nodeptr _Max(_Nodeptr _Pnode)
  {       // return rightmost node in subtree at _Pnode
    return static_cast<_Nodeptr>(_Mybase::_Max(_Pnode));
  }

  static _Nodeptr _Min(_Nodeptr _Pnode)
  {       // return leftmost node in subtree at _Pnode
    return static_cast<_Nodeptr>(_Mybase::_Min(_Pnode));
  }

  _Nodepref _Rmost()
  {       // return rightmost node in mutable tree
    return (_Right(_Head())); 
  }

  _Nodepref _Rmost() const
  {       // return rightmost node in nonmutable tree
    return (_Right(_Head())); 
  }

  _Nodepref _Root()
  {       // return root of mutable tree
    return (_Parent(_Head())); 
  }

  _Nodepref _Root() const
  {       // return root of nonmutable tree
    return (_Parent(_Head())); 
  }

  _Nodeptr _Head() const
  {
    return (_Nodeptr)(&this->_Myhead);
  }

  void _Rrotate(_Nodeptr _Wherenode)
  {       // promote left node to root of subtree
    _Mybase::_Rrotate(_Wherenode);
  }

  _Nodeptr _Ubound(_KeyParamTy _Keyval) const
  {       // find leftmost node greater than _Keyval
    _Nodeptr _Pnode = _Root();
    _Nodeptr _Wherenode = _Head();  // end() if search fails

    while (!_Isnil(_Pnode))
      if (this->comp()(_Keyval, _Key(_Pnode)))
      {       // _Pnode greater than _Keyval, remember it
        _Wherenode = _Pnode;
        _Pnode = _Left(_Pnode);        // descend left subtree
      }
      else
        _Pnode = _Right(_Pnode);        // descend right subtree

    return (_Wherenode);   // return best remembered candidate
  }

  _Nodeptr _Buynode(_Nodeptr _Larg, _Nodeptr _Parg, _Nodeptr _Rarg,
                    _ValParamTy _Val, char _Carg)
  {       // allocate a node with pointers, value, and color
    _Nodeptr _Wherenode = this->_Alnod().allocate(1);
    _TRY_BEGIN
      new (_Wherenode) _Node(_Larg, _Parg, _Rarg, _Val, _Carg);
    _CATCH_ALL
      this->_Alnod().deallocate(_Wherenode, 1);
    _RERAISE;
    _CATCH_END
      return (_Wherenode); 
  }
};

// _Tree TEMPLATE OPERATORS
template<class _Traits> inline
void swap(_Tree<_Traits>& _Left, _Tree<_Traits>& _Right)
{       // swap _Left and _Right trees
  _Left.swap(_Right); 
}

template<class _Traits> inline
bool operator==(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right)
{       // test for _Tree equality
  return (_Left.size() == _Right.size()
          && equal(_Left.begin(), _Left.end(), _Right.begin())); 
}

template<class _Traits> inline
bool operator!=(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right)
{       // test for _Tree inequality
  return (!(_Left == _Right)); 
}

template<class _Traits> inline
bool operator<(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right)
{       // test if _Less < _Right for _Trees
  return (lexicographical_compare(_Left.begin(), _Left.end(),
                                  _Right.begin(), _Right.end())); 
}

template<class _Traits> inline
bool operator>(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right)
{       // test if _Less > _Right for _Trees
  return (_Right < _Left); 
}

template<class _Traits> inline
bool operator<=(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right)
{       // test if _Less <= _Right for _Trees
  return (!(_Right < _Left)); 
}

template<class _Traits> inline
bool operator>=(const _Tree<_Traits>& _Left, const _Tree<_Traits>& _Right)
{       // test if _Less >= _Right for _Trees
  return (!(_Left < _Right)); 
}

_STD_END
#endif /* _XTREE_ */

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation for any purpose is hereby
 * granted without fee, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
 */

/*
 * Copyright (c) 1992-2009 by P.J. Plauger.  ALL RIGHTS RESERVED.
 * Consult your license regarding permissions and restrictions.
 V5.04:0576 */
